QUnit.module('RedBlackTree', () =>
{
    QUnit.test('should always color first inserted node as black', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const firstInsertedNode = tree.insert(10);

        assert.deepEqual(tree.isNodeColored(firstInsertedNode), true);
        assert.deepEqual(tree.isNodeBlack(firstInsertedNode), true);
        assert.deepEqual(tree.isNodeRed(firstInsertedNode), false);

        assert.deepEqual(tree.toString(), '10');
        assert.deepEqual(tree.root.height, 0);
    });

    QUnit.test('should always color new leaf node as red', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const firstInsertedNode = tree.insert(10);
        const secondInsertedNode = tree.insert(15);
        const thirdInsertedNode = tree.insert(5);

        assert.deepEqual(tree.isNodeBlack(firstInsertedNode), true);
        assert.deepEqual(tree.isNodeRed(secondInsertedNode), true);
        assert.deepEqual(tree.isNodeRed(thirdInsertedNode), true);

        assert.deepEqual(tree.toString(), '5,10,15');
        assert.deepEqual(tree.root.height, 1);
    });

    QUnit.test('should balance itself', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        tree.insert(5);
        tree.insert(10);
        tree.insert(15);
        tree.insert(20);
        tree.insert(25);
        tree.insert(30);

        assert.deepEqual(tree.toString(), '5,10,15,20,25,30');
        assert.deepEqual(tree.root.height, 3);
    });

    QUnit.test('should balance itself when parent is black', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const node1 = tree.insert(10);

        assert.deepEqual(tree.isNodeBlack(node1), true);

        const node2 = tree.insert(-10);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeRed(node2), true);

        const node3 = tree.insert(20);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeRed(node2), true);
        assert.deepEqual(tree.isNodeRed(node3), true);

        const node4 = tree.insert(-20);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeRed(node4), true);

        const node5 = tree.insert(25);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);

        const node6 = tree.insert(6);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);
        assert.deepEqual(tree.isNodeRed(node6), true);

        assert.deepEqual(tree.toString(), '-20,-10,6,10,20,25');
        assert.deepEqual(tree.root.height, 2);

        const node7 = tree.insert(4);

        assert.deepEqual(tree.root.left.value, node2.value);

        assert.deepEqual(tree.toString(), '-20,-10,4,6,10,20,25');
        assert.deepEqual(tree.root.height, 3);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeRed(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeBlack(node4), true);
        assert.deepEqual(tree.isNodeBlack(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);
        assert.deepEqual(tree.isNodeBlack(node6), true);
        assert.deepEqual(tree.isNodeRed(node7), true);
    });

    QUnit.test('should balance itself when uncle is red', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const node1 = tree.insert(10);
        const node2 = tree.insert(-10);
        const node3 = tree.insert(20);
        const node4 = tree.insert(-20);
        const node5 = tree.insert(6);
        const node6 = tree.insert(15);
        const node7 = tree.insert(25);
        const node8 = tree.insert(2);
        const node9 = tree.insert(8);

        assert.deepEqual(tree.toString(), '-20,-10,2,6,8,10,15,20,25');
        assert.deepEqual(tree.root.height, 3);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeRed(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeBlack(node4), true);
        assert.deepEqual(tree.isNodeBlack(node5), true);
        assert.deepEqual(tree.isNodeRed(node6), true);
        assert.deepEqual(tree.isNodeRed(node7), true);
        assert.deepEqual(tree.isNodeRed(node8), true);
        assert.deepEqual(tree.isNodeRed(node9), true);

        const node10 = tree.insert(4);

        assert.deepEqual(tree.toString(), '-20,-10,2,4,6,8,10,15,20,25');
        assert.deepEqual(tree.root.height, 3);

        assert.deepEqual(tree.root.value, node5.value);

        assert.deepEqual(tree.isNodeBlack(node5), true);
        assert.deepEqual(tree.isNodeRed(node1), true);
        assert.deepEqual(tree.isNodeRed(node2), true);
        assert.deepEqual(tree.isNodeRed(node10), true);
        assert.deepEqual(tree.isNodeRed(node6), true);
        assert.deepEqual(tree.isNodeRed(node7), true);
        assert.deepEqual(tree.isNodeBlack(node4), true);
        assert.deepEqual(tree.isNodeBlack(node8), true);
        assert.deepEqual(tree.isNodeBlack(node9), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
    });

    QUnit.test('should do left-left rotation', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const node1 = tree.insert(10);
        const node2 = tree.insert(-10);
        const node3 = tree.insert(20);
        const node4 = tree.insert(7);
        const node5 = tree.insert(15);

        assert.deepEqual(tree.toString(), '-10,7,10,15,20');
        assert.deepEqual(tree.root.height, 2);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);

        const node6 = tree.insert(13);

        assert.deepEqual(tree.toString(), '-10,7,10,13,15,20');
        assert.deepEqual(tree.root.height, 2);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node5), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node6), true);
        assert.deepEqual(tree.isNodeRed(node3), true);
    });

    QUnit.test('should do left-right rotation', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const node1 = tree.insert(10);
        const node2 = tree.insert(-10);
        const node3 = tree.insert(20);
        const node4 = tree.insert(7);
        const node5 = tree.insert(15);

        assert.deepEqual(tree.toString(), '-10,7,10,15,20');
        assert.deepEqual(tree.root.height, 2);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);

        const node6 = tree.insert(17);

        assert.deepEqual(tree.toString(), '-10,7,10,15,17,20');
        assert.deepEqual(tree.root.height, 2);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node6), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);
        assert.deepEqual(tree.isNodeRed(node3), true);
    });

    QUnit.test('should do recoloring, left-left and left-right rotation', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const node1 = tree.insert(10);
        const node2 = tree.insert(-10);
        const node3 = tree.insert(20);
        const node4 = tree.insert(-20);
        const node5 = tree.insert(6);
        const node6 = tree.insert(15);
        const node7 = tree.insert(30);
        const node8 = tree.insert(1);
        const node9 = tree.insert(9);

        assert.deepEqual(tree.toString(), '-20,-10,1,6,9,10,15,20,30');
        assert.deepEqual(tree.root.height, 3);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeRed(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeBlack(node4), true);
        assert.deepEqual(tree.isNodeBlack(node5), true);
        assert.deepEqual(tree.isNodeRed(node6), true);
        assert.deepEqual(tree.isNodeRed(node7), true);
        assert.deepEqual(tree.isNodeRed(node8), true);
        assert.deepEqual(tree.isNodeRed(node9), true);

        tree.insert(4);

        assert.deepEqual(tree.toString(), '-20,-10,1,4,6,9,10,15,20,30');
        assert.deepEqual(tree.root.height, 3);
    });

    QUnit.test('should do right-left rotation', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        const node1 = tree.insert(10);
        const node2 = tree.insert(-10);
        const node3 = tree.insert(20);
        const node4 = tree.insert(-20);
        const node5 = tree.insert(6);
        const node6 = tree.insert(30);

        assert.deepEqual(tree.toString(), '-20,-10,6,10,20,30');
        assert.deepEqual(tree.root.height, 2);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node3), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);
        assert.deepEqual(tree.isNodeRed(node6), true);

        const node7 = tree.insert(25);

        const rightNode = tree.root.right;
        const rightLeftNode = rightNode.left;
        const rightRightNode = rightNode.right;

        assert.deepEqual(rightNode.value, node7.value);
        assert.deepEqual(rightLeftNode.value, node3.value);
        assert.deepEqual(rightRightNode.value, node6.value);

        assert.deepEqual(tree.toString(), '-20,-10,6,10,20,25,30');
        assert.deepEqual(tree.root.height, 2);

        assert.deepEqual(tree.isNodeBlack(node1), true);
        assert.deepEqual(tree.isNodeBlack(node2), true);
        assert.deepEqual(tree.isNodeBlack(node7), true);
        assert.deepEqual(tree.isNodeRed(node4), true);
        assert.deepEqual(tree.isNodeRed(node5), true);
        assert.deepEqual(tree.isNodeRed(node3), true);
        assert.deepEqual(tree.isNodeRed(node6), true);
    });

    QUnit.test('should do left-left rotation with left grand-parent', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        tree.insert(20);
        tree.insert(15);
        tree.insert(25);
        tree.insert(10);
        tree.insert(5);

        assert.deepEqual(tree.toString(), '5,10,15,20,25');
        assert.deepEqual(tree.root.height, 2);
    });

    QUnit.test('should do right-right rotation with left grand-parent', (assert) =>
    {
        const tree = new ds.RedBlackTree();

        tree.insert(20);
        tree.insert(15);
        tree.insert(25);
        tree.insert(17);
        tree.insert(19);

        assert.deepEqual(tree.toString(), '15,17,19,20,25');
        assert.deepEqual(tree.root.height, 2);
    });

    QUnit.test('should throw an error when trying to remove node', (assert) =>
    {
        const removeNodeFromRedBlackTree = () =>
        {
            const tree = new ds.RedBlackTree();

            tree.remove(1);
        };

        var error0 = false;

        try
        {
            removeNodeFromRedBlackTree();
        } catch (error)
        {
            error0 = true;
        }
        assert.deepEqual(error0, true);
    });
});
